package com.demo.java.OD451_500.OD456;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【中文分词模拟器(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146341294
 */
public class OdMain {
    // 根据字典分割字符串
    public static List<String> segmentString(String inputStr,
                                             List<String> dictionary) {
        List<String> result = new ArrayList<>();
        int i = 0;
        int n = inputStr.length();

        // 遍历字符串
        while (i < n) {
            boolean found = false;
            // 优先匹配较长的单词
            for (String word : dictionary.stream().sorted((s1,
                                                           s2) -> Integer.compare(s2.length(), s1.length())).toArray(String[]::new)) {
                if (i + word.length() <= n &&
                        inputStr.substring(i, i + word.length()).equals(word)) {
                    result.add(word);  // 找到匹配的单词
                    i += word.length();  // 更新当前的位置
                    found = true;
                    break;
                }
            }

            // 如果没有找到匹配的单词，将当前字符作为单独一个部分
            if (!found) {
                result.add(inputStr.substring(i, i + 1));
                i++;
            }
        }

        // 过滤掉空字符串和单独的逗号
        List<String> output = new ArrayList<>();
        for (String word : result) {
            if (!word.isEmpty() && !word.equals(",")) {
                output.add(word);
            }
        }

        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取输入字符串
        String inputStr = scanner.nextLine().trim();

        // 读取字典并拆分成单词
        String[] dictionaryArray = scanner.nextLine().trim().split(",");
        List<String> dictionary = Arrays.asList(dictionaryArray);

        // 调用分割函数并输出结果
        List<String> output = segmentString(inputStr, dictionary);
        System.out.println(String.join(",", output));

        scanner.close();
    }
}